package com.lx.algorithm.prefixTree;

import org.springframework.util.StringUtils;

/**
 * Description: 前缀树
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-19 14:26:32
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-19     张李鑫                     1.0         1.0 Version
 */
public class PrefixTree {
    private Node root;

    public static class Node {
        //经过几次
        private Integer pass;
        //多少自付以此为结尾
        private Integer end;
        //代表有多少路
        private Node[] list;

        public Node() {
            //练习只做26个小写字母的排序
            list = new Node[26];
            pass = 0;
            end = 0;
        }
    }

    public PrefixTree() {
        root = new Node();
    }


    /**
     * <p>
     *    新增某个字符串
     * </p>
     * @param  val
     * @return void
     * @Author zlx
     * @date 2021/9/19
     */
    public void insert(String val) {
        if (StringUtils.isEmpty(val)) {
            return;
        }
        Node node = root;
        char[] chars = val.toCharArray();
        root.pass++;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (null == node.list[index]) {
                node.list[index] = new Node();
            }
            node = node.list[index];
            node.pass++;
        }
        node.end++;
    }

    /**
     * <p>
     *   删除某个字符串
     * </p>
     * @param  val
     * @return void
     * @Author zlx
     * @date 2021/9/19
     */
    public void delete(String val) {
        if (search(val) == 0) {
            return;
        }
        Node node = root;
        node.pass--;
        char[] chars = val.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            //小优化 判断当前值是否等于1 如果等于1的话 直接断链 节省空间
            if (--node.list[index].pass==0){
                node.list[index]=null;
                return;
            }
            node = node.list[index];
        }
        node.end--;
    }

    /**
     * <p>
     *    查找当前字符串出现了几次
     * </p>
     * @param  val
     * @return int
     * @Author zlx
     * @date 2021/9/19
     */
    public int search(String val) {
        if (StringUtils.isEmpty(val)) {
            return 0;
        }
        Node node = root;
        char[] chars = val.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (node.list[index] != null) {
                node = node.list[index];
            } else {
                return 0;
            }
        }
        return node.end;
    }

    /**
     * <p>
     *    找的是有几个以此为前缀的字符所以返回的是pass
     * </p>
     * @param  val
     * @return int
     * @Author zlx
     * @date 2021/9/19
     */
    public int prefixNumber(String val) {
        if (StringUtils.isEmpty(val)) {
            return 0;
        }
        Node node = root;
        char[] chars = val.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (node.list[index] != null) {
                node = node.list[index];
            } else {
                return 0;
            }
        }
        return node.pass;
    }



}